1. Field of the Invention
The present invention relates to a real-time schedulability determination method for determining whether real-time scheduling of a plurality of tasks is possible using a plurality of processors, and a real-time system employing the method.
2. Description of the Related Art
Real-time systems are time-constrained computer systems in which “processing of any task must be completed within a time limit set for it”.
In general, the time limit set for each task is called a “deadline”, and if a task is not completed by its deadline, this is called a “deadline miss”. Real-time systems must be absolutely free from deadline misses.
Air traffic control systems, plant control monitoring systems, medical systems, etc., are typical real-time systems. Air traffic control systems, for example, set a safety interval between airplanes or between an airplane and an obstacle in order to prevent collisions of airplanes. In this case, if two seconds are required to determine whether airplanes will collide with each other within a second, this is useless. Thus, air traffic control systems are under strict time constraints.
Operation of machines under strict time constraints under which deadline misses are unallowable is called “real-time scheduling”. Various methods for realizing real-time scheduling have been proposed so far.
For example, a technique for performing real-time scheduling using the earliest deadline first (EDF) algorithm is known (see, for example, J. W. S. Liu, “Real-time Systems”, Prentice Hall, 2000)
In real-time scheduling, it is important to assign appropriate processors to respective appropriate tasks for respective appropriate periods in order to prevent each task from occurring a deadline miss.
When real-time scheduling of a plurality of tasks using a plurality of processors is performed, it is firstly determined, using a real-time schedulability determination method, whether the processors can perform real-time scheduling of tasks, and secondly, only if such real-time scheduling is determined to be possible, it is determined, using an appropriate scheduling method, which processor, task and period should be combined.
In the EDF algorithm as a typical scheduling method, a processor is preferentially assigned at the earliest time to a task with the earliest deadline.
A real-time schedulability determination method is known in which real-time scheduling is possible using the EDF algorithm. Concerning this technique, see, for example, T. P. Baker, “An Analysis of EDF Schedulability on a Multiprocessor”, FSU Computer Science Technical Report TR-030202, 2003 (this will hereinafter be referred to as “Baker”).
Another real-time schedulability determination method is known in which scheduling is virtually executed to check whether a deadline miss will occur. Concerning this technique, see, for example, J. F. Hermant et al., “Real-time Fixed and Dynamic Priority Driven Scheduling Algorithms: Theory and Experience”, Inria Technical Report, 1996 (this will hereinafter be referred to as “Hermant et al.”).
In the description below, unless otherwise specified, real-time schedulability and non-schedulability will be referred to simply as “schedulability” and “non-schedulability”, respectively.
However, in the determination method disclosed in Baker, it is assumed that only a single processor is assigned to a single task. In other words, this method does not consider a task that simultaneously requires a plurality of processor to enhance processing efficiency. Therefore, a schedulability determination method is demanded which can also be utilized when a plurality of processors are simultaneously needed to process a single task.
Furthermore, the method disclosed in Hermant et al., in which virtual scheduling is performed, is unrealistic since it requires a long calculation time.